package algorithm;

import java.util.*;
import java.util.stream.Collectors;

//八皇后
public class EightQueue {
    public static final int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
    public static final int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};


    public static void main(String[] args) {
        int count = 8;
        int[][] attck = new int[count][count];
        List<String> queen = new ArrayList<>();
        List<List<String>> solve = new ArrayList<>();

        //初始化
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < count; j++) {
                attck[i][j] = 0;
            }
        }
        for (int i = 0; i < count; i++) {
            StringBuilder stringBuilder=new StringBuilder();
            for (int j = 0; j < count; j++) {
                stringBuilder.append(".");
            }
            queen.add(stringBuilder.toString());
        }

        EightQueue e = new EightQueue();
        e.backtrace(0, count, queen, attck, solve);
        System.out.println(solve);
    }

    //K 当前处理的行
    public void backtrace(int k, int n, List<String> queen,
                          int[][] attack, List<List<String>> solve) {
        if (k == n) {
            List<String> res = List.copyOf(queen);
            solve.add(res);
            return;
        }

        //i 列
        for (int i = 0; i < n; i++) {
            if (attack[k][i] == 0) {
                int[][] tmp = new int[n][n];
                for (int j = 0; j < n; j++) {
                    tmp[j] = attack[j].clone();
                }

                char[] charArray = queen.get(k).toCharArray();
                charArray[i] = 'Q';
                queen.remove(k);
                queen.add(k, new String(charArray));

                putQueen(k, i, attack);
                backtrace(k + 1, n, queen, attack, solve);
                attack = tmp;

                charArray = queen.get(k).toCharArray();
                charArray[i] = '.';
                queen.remove(k);
                queen.add(k, new String(charArray));
            }
        }
    }

    private void putQueen(int k, int i, int[][] attack) {
        attack[k][i] = 1;

        for (int d = 0; d < 8; d++) {
            int count = 1;
            int tmpX = k + count * dx[d];
            int tmpY = i + count * dy[d];
            while (tmpY >= 0 && tmpY < attack.length && tmpX >= 0 && tmpX < attack.length) {
                attack[tmpX][tmpY] = 1;
                count++;
                tmpX = k + count * dx[d];
                tmpY = i + count * dy[d];
            }
        }
    }
}
